use std::cell::RefCell;
use std::cmp::max;
use std::collections::VecDeque;
use std::rc::Rc;
use crate::data_structure::tree_node::TreeNode;

/*
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}
*/


// 实现TreeNode结构体,名称如果使用TreeNodeUse的话，测试里报错Option<Rc<RefCell<TreeNodeUse>>>
impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None
        }
    }

    // 通过数组反序列化生成一棵树(一维向量/数组转二叉树)
    pub fn vec1d_to_tree_node(nums: Vec<Option<i32>>) -> Option<Rc<RefCell<Self>>> {
        if nums.is_empty() {
            return None;
        }
        let size = nums.len();
        let mut index = 0;
        let root = Some(Rc::new(RefCell::new(Self::new(nums[0].unwrap()))));
        let mut queue = VecDeque::new();
        queue.push_back(root.clone());
        while !queue.is_empty() {
            let q_size = queue.len();
            for _i in 0..q_size {
                if let Some(x) = queue.pop_front().flatten() {
                    // borrow()方法返回内部包装对象的只读引用。
                    // borrow_mut()返回内部包装对象的可写引用。
                    let mut node = x.borrow_mut();
                    let lseq = 2 * index + 1;
                    let rseq = 2 * index + 2;
                    if lseq < size && nums[lseq].is_some() {
                        node.left = Some(Rc::new(RefCell::new(Self::new(nums[lseq].unwrap()))));
                        queue.push_back(node.left.clone());
                    }

                    if rseq < size && nums[rseq].is_some() {
                        node.right = Some(Rc::new(RefCell::new(Self::new(nums[rseq].unwrap()))));
                        queue.push_back(node.right.clone());
                    }
                }
                index += 1;
            }
        }
        root
    }

    // 将一棵树序列化(literal)成一个数组(二叉树转一维向量/数组)
    pub fn tree_node_to_vec1d(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<i32>> {
        if root.is_none() {
            return vec![];
        }
        let mut ans = vec![];
        let mut queue = VecDeque::new();
        queue.push_back(root);
        while !queue.is_empty() {
            let qsize = queue.len();
            for _ in 0..qsize {
                match queue.pop_front().flatten() {
                    Some(x) => {
                        ans.push(Some(x.borrow().val));
                        queue.push_back(x.borrow().left.clone());
                        queue.push_back(x.borrow().right.clone());
                    }
                    None => ans.push(None),
                }
            }
        }
        let size = ans.len();
        for i in (0..size).rev() {
            if ans[i].is_none() {
                ans.pop();
            } else {
                break;
            }
        }
        ans
    }

    // 获取二叉树高度
    pub fn get_tree_node_height(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            match root {
                None => 0,
                Some(node) => {
                    let node = node.borrow();
                    // 返回值，直接没有return标识
                    1 + max(dfs(&node.left), dfs(&node.right))
                }
            }
        }
        dfs(&root)
    }

    // leetcode 655. 输出二叉树(树的拓扑树形进行打印)(leetcode这个题输出的是vec，和这个不太一样!!)
    pub fn print_tree_as_string(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        // 二叉树高度
        let height = TreeNode::get_tree_node_height(&root);
        // 满二叉树的宽度
        let width = (1 << height) - 1;
        let mut ans = vec![vec![" ".to_string(); width as usize]; height as usize];

        // dfs 搜索
        fn dfs(ans: &mut Vec<Vec<String>>, node: &Option<Rc<RefCell<TreeNode>>>, deep: usize, lo: usize, hi: usize) {
            if let Some(x) = node {
                let node = x.borrow();
                let mid = lo + (hi - lo) / 2;
                ans[deep][mid] = x.borrow().val.to_string();
                dfs(ans, &node.left, deep + 1, lo, mid);
                dfs(ans, &node.right, deep + 1, mid + 1, hi);
            }
        }

        dfs(&mut ans, &root, 0usize, 0usize, width as usize);
        // 将所有字符连起来
        ans.iter().map(|x| x.concat()).collect::<Vec<_>>().join("\n")
    }


}



#[cfg(test)]
mod tests {
    // use super::*;
    // 上面引入，测试里也要引入，要不报错！
    use crate::data_structure::tree_node::TreeNode;

    #[test]
    fn test_vec1d_to_tree_node() {
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            Some(4), None, Some(5), Some(6),
            None, Some(7), None, None, Some(8)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);
        // Some(RefCell { value: TreeNode { val: 1, left: Some(RefCell { value: TreeNode { val: 2, left: Some(RefCell { value: TreeNode { val: 4, left: None, right: Some(RefCell { value: TreeNode { val: 7, left: None, right: None } }) } }), right: None } }), right: Some(RefCell { value: TreeNode { val: 3, left: Some(RefCell { value: TreeNode { val: 5, left: None, right: None } }), right: Some(RefCell { value: TreeNode { val: 6, left: Some(RefCell { value: TreeNode { val: 8, left: None, right: None } }), right: None } }) } }) } })
        println!("{:?}", root);

    }

    #[test]
    fn test_tree_node_to_vec1d() {
        // 先构造一个二叉树root:
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            Some(4), None, Some(5), Some(6),
            None, Some(7), None, None, Some(8)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);

        let ans = TreeNode::tree_node_to_vec1d(root);
        // [Some(1), Some(2), Some(3), Some(4), None, Some(5), Some(6), None, Some(7), None, None, Some(8)]
        println!("ans: \n{:?}", ans);
    }

    #[test]
    fn test_print_tree_as_string() {
        // 先构造一个二叉树root:
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            Some(4), None, Some(5), Some(6),
            None, Some(7), None, None, Some(8)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);

        // 调用测试的函数
        let tree = TreeNode::print_tree_as_string(root);
        // "       1       \n   2       3   \n 4       5   6 \n  7         8  "
        // println!("tree:\n{:?}", tree);
        /*
               1
           2       3
         4       5   6
          7         8
        */
        println!("tree:\n{}", tree); // 字符串用这个{}!!
    }

    #[test]
    fn test_1() {
        let s = "       1       \n   2       3   \n 4       5   6 \n  7         8  ";
        println!("{}", s);
        /*
               1
           2       3
         4       5   6
          7         8
        */
        // 树的拓扑树形打印，打印出来还是很漂亮的!
    }

    #[test]
    fn test_2() {
        let head = [2,7,4,3,5].to_vec();
        // 转换为Vec<Option<i32>>
        let option_vec: Vec<Option<i32>> = head.into_iter().map(|num| Some(num)).collect();
        println!("{:?}", option_vec);
        let root = TreeNode::vec1d_to_tree_node(option_vec);
        println!("{:?}", root);
    }

}


